Collective Construction of 2D Block Structures with Holes

摘要

In this paper we present algorithms for collective construction systems inwhich a large number of autonomous mobile robots trans- port modular buildingelements to construct a desired structure. We focus on building blockstructures subject to some physical constraints that restrict the order inwhich the blocks may be attached to the structure. Specifically, we determine apartial ordering on the blocks such that if they are attached in accordancewith this ordering, then (i) the structure is a single, connected piece at allintermediate stages of construction, and (ii) no block is attached between twoother previously attached blocks, since such a space is too narrow for a robotto maneuver a block into it. Previous work has consider this problem forbuilding 2D structures without holes. Here we extend this work to 2D structureswith holes. We accomplish this by modeling the problem as a graph orientationproblem and describe an O(n^2) algorithm for solving it. We also describe howthis partial ordering may be used in a distributed fashion by the robots tocoordinate their actions during the building process.